//#include<iostream>
//#include<vector>
//using namespace std;
////
////class Solution {
////public:
////    void duplicateZeros(vector<int>& arr) 
////    {
////        int len = arr.size();
////        int cur = 0;;
////        int dest = -1;
////        while (dest<len)
////        {
////            if (arr[cur] != 0)
////            {
////                ++dest;
////                ++cur;
////            }
////            else
////            {
////                dest += 2;
////                ++cur;
////            }
////        }
////        if (dest == len)
////        {
////            dest -= 2;
////            cur--;
////            arr[len - 1] = 0;
////        }
////        while (cur>=0)
////        {
////            if (arr[cur])swap(arr[cur--], arr[dest--]);
////            else
////            {
////                arr[dest--] = 0;
////                arr[dest--] = 0;
////                --cur;
////            }
////        }
////    }
////};
//
//
//class Solution 
//{
//public:
//    int sqsum(int n)
//    {
//        int sum = 0;
//        while (n)
//        {
//
//            int i = n % 10;
//            sum = sum + i * i;
//            n /= 10;
//        }
//        return sum;
//    }
//    bool isHappy(int n)
//    {
//        int slow = n; int fast = sqsum(n);
//        while (slow != fast)
//        {
//            slow = sqsum(slow);
//            fast = sqsum(sqsum(fast));
//        }
//        return slow == 1;
//    }
//};
//
//
//int sqsum(int n)
//{
//    int sum = 0;
//    int i;
//    while (n)
//    {
//        i = n % 10;
//        sum = sum + i * i;
//        n /= 10;
//    }
//    return sum;
//}
//int main()
//{
//    int i = 0;
//    cin >> i;
//    cout << sqsum(i) << endl;
//
//	return 0;
//};


#include<iostream>
#include<vector>
using namespace std;

//int main()
//{
//	int n, q;
//	cin >> n >> q;
//	vector<int> v;
//	vector<vector<int>> vv(n,v);
//	while (q--)
//	{
//		int m,i, j, k=0;
//		cin >> m;
//		switch (m)
//		{
//		case 1:
//			cin >> i >> j >> k;
//			if (vv[i].size() <= j)
//			{
//				vv[i].resize(j + 1);
//			}
//			vv[i][j] = k;
//			break;
//		case 2:
//			cin >> i >> j;
//			if (vv[i].size() <= j)
//			{
//				vv[i].resize(j + 1);
//			}
//			vv[i][j] = 0;
//			cout << vv[i][j] << endl;
//		}
//
//	}
//	return 0;
//}



class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        vector<int> v(2);
        int right = price.size() - 1;
        int left = 0;
        while (left < right)
        {
            if (price[left] + price[right] == target)
            {
                v[0] = price[left];
                v[1] = price[right];
            }
            else if (price[left] + price[right] > target)
            {
                --right;
            }
            else
                ++left;
        }
        return v;
    }
};

int main()
{
    vector<int> price = { 3, 9, 12, 15 };
    int target=18;
    Solution s;
    s.twoSum(price, target);

    return 0;
}